package com.leetcode.no112;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null) {
            return sum == root.val;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

    }

    public boolean hasPathSum01(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<>();
        Queue<Integer> queVal = new LinkedList<>();


        queNode.offer(root);
        queVal.offer(root.val);


        while (!queNode.isEmpty()) {
            TreeNode tmpNode = queNode.poll();
            int tmpVal = queVal.poll();

            if (tmpNode.left == null && tmpNode.right == null) {
                if (tmpVal == sum) return true;
                continue;
            }
            if(tmpNode.left!=null){
                queNode.offer(tmpNode.left);
                queVal.offer(tmpNode.left.val+tmpVal);
            }
            if(tmpNode.right!=null){
                queNode.offer(tmpNode.right);
                queVal.offer(tmpNode.right.val + tmpVal);
            }
        }

        return false;
    }
}
